package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by 朱城委 on 2021/8/31.<br><br>
 *
 * 中等：复原IP地址
 */
public class Topic93 {

    public static void main(String[] args) {
        Topic93 instance = new Topic93();

        System.out.println(instance.restoreIpAddresses("25525511135"));
        System.out.println(instance.restoreIpAddresses("0000"));
        System.out.println(instance.restoreIpAddresses("1111"));
        System.out.println(instance.restoreIpAddresses("010010"));
        System.out.println(instance.restoreIpAddresses("101023"));
    }

    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();

        helper(s, "", result, 0, 0);
        return result;
    }

    private void helper(String s, String ip, List<String> result, int index, int count) {
        if(count > 4) {
            return ;
        }

        if(count == 4 && index == s.length()) {
            result.add(ip);
            return ;
        }

        for(int i = 1; i <= 3; i++) {
            if(index + i > s.length()) {
                break;
            }

            String temp = s.substring(index, index + i);
            if((temp.length() > 1 && temp.charAt(0) == '0') || (Integer.parseInt(temp) > 255)) {
                break;
            }

            helper(s, ip + temp + (count == 3 ? "" : "."), result, index + i, count + 1);
        }
    }
}
